#include <bits/stdc++.h>

using namespace std;

// 求树节点的第 K 个祖先（树上倍增算法）
// 有关LCA问题的介绍：https://oi-wiki.org/graph/lca/
// LCA模板见灵神题解，链接如下：
// https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/
// 测试链接：https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/

class TreeAncestor
{
private:
    vector<vector<int>> fa;

    // 返回尾随零的个数
    int numberOfTrailingZeros(int a)
    {
        for(int i = 0; i != 32; ++i)
        {
            if((a >> i) & 1) return i;
        }
        return 0;
    }

    // 返回前导零的个数
    int numberOfLeadingZeros(int a)
    {
        for(int i = 0; i != 32; ++i)
        {
            if((a >> (31 - i)) & 1) return i;
        }
        return 0;
    }

public:
    TreeAncestor(int n, vector<int> &parent)
    {
        int m = 32 - __builtin_clz(n);
        // int m = 32 - numberOfLeadingZeros(n);
        fa.resize(n, vector<int>(m, -1));
        for (int i = 0; i < n; ++i)
        {
            fa[i][0] = parent[i];
        }

        for (int i = 0; i < m - 1; ++i)
        {
            for (int x = 0; x < n; ++x)
            {
                if (int p = fa[x][i]; p != -1)
                {
                    fa[x][i + 1] = fa[p][i];
                }
            }
        }
    }

    int getKthAncestor(int node, int k)
    {
        for (; k && node != -1; k &= k - 1)
        {
            // node = fa[node][numberOfTrailingZeros(k)];
            node = fa[node][__builtin_ctz(k)];
        }
        return node;
    }

    int getKthAncestor2(int node, int k)
    {
        int m = 32 - numberOfLeadingZeros(k);
        for (int i = 0; i < m; i++)
        {
            if ((k >> i) & 1)
            {
                node = fa[node][i];
                if (node < 0)
                    break;
            }
        }
        return node;
    }
};